package com.zang.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/combinations/discussion/">...</a>
 * 没有额外条件属于基础回溯题目
 * @author ZVerify
 * @since 2022/11/07 11:39
 **/
public class 组合 {

    // 每次的结果
    List<Integer> list =  new ArrayList<>();
    // 最终的结果
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {

        // 进入递归
        backtrack(1,n,k);
        return result;
    }

    private void backtrack(int start, int end, int length) {
        // 长度到了就结束
        if (list.size() == length) {
            result.add(new ArrayList<>(list));
        }

        for (int i = start; i <= end; i++) {
            // 添加
            list.add(i);
            // 递归
            backtrack(i+1, end, length);
            // 回溯
            list.remove(list.size() - 1);
        }
    }


}
